package 数组题目.前缀和与差分;

import java.util.HashMap;

//连续的子数组和
//https://leetcode.cn/problems/continuous-subarray-sum/
//给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个 `好的子数组` 返回 true ，否则返回 false
//一个 `好的子数组` 是：长度至少为2，且子数组元素总和为 k 的倍数。
//注意:子数组 是数组中 连续 的部分。
class 连续的子数组和 {
    //寻找 i, j 使得 (numsSum[i] - numsSum[j]) % k == 0 且 i - j >= 2。
    //另外，(numsSum[i] - numsSum[j]) % k == 0 其实就是 numsSum[i] % k == numsSum[j] % k。
    //所以我们使用一个哈希表，记录 numsSum[j] % k 的值以及对应的索引，就可以迅速判断 numsSum[i] 是否符合条件了。
    public boolean checkSubarraySum(int[] nums, int k) {
        // 求出前缀和
        int[] numsSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            numsSum[i + 1] = nums[i] + numsSum[i];
            //求和过程中遇到 %k == 0 直接返回ture
            if (i >= 1 && numsSum[i + 1] % k == 0) {
                return true;
            }
        }
        // 用哈希表存储 numsSum[j] % k 对应的索引
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numsSum.length; i++) {
            int val = numsSum[i] % k;
            if (!map.containsKey(val)) {
                map.put(val, i);
            } else {
                // 判断是否存在 numsSum[i] 使得 (numsSum[i] - need) % k == 0
                if (i - map.get(val) >= 2) {
                    // 这个子数组的长度至少为 2
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
//        System.out.println(new Solution().checkSubarraySum(new int[]{23, 2, 4, 6, 7}, 6));
//        System.out.println(new Solution().checkSubarraySum(new int[]{23, 2, 6, 4, 7}, 13));
        System.out.println(new 连续的子数组和().checkSubarraySum(new int[]{2, 4, 3}, 6));
    }
}
